Legacy cryptographic algorithms and protocols developed over 30 years ago, e.g., triple-DES, RSA, and SHA-1, are becoming obsolete and are at risk of being compromised or “broken” in the relatively near future. More advanced algorithms are available and have been adopted as a standard by the U.S. Government and other countries, including but not limited to the set of unclassified algorithms called “Suite B,” consisting of Elliptic Curve Cryptography (ECC), the Advanced Encryption Standard (AES), and the new family of Secure Hash Algorithms generically referred to as “SHA-2.” Those skilled in the art of cryptography will recognize that other cryptographic algorithms could be substituted for the Suite B algorithms with equal effect, potentially including but not limited to those classified algorithms and protocols that make up the “Suite A” algorithms used exclusively by the U.S. Government, as well as other proprietary and/or classified algorithms used elsewhere in the world.
However, directly incorporating these advanced algorithms within existing operating systems and/or cryptographic applications would require extensive rewrites at a significant cost and with a substantial delay in widespread availability to take advantage of them. In addition, the introduction of such advanced algorithms cannot be accomplished with the flick of a switch, but instead must be phased in over time. In general, this phased introduction will give rise to serious interoperability problems, with a portion of the community not being able to communicate with others until the conversion has been completed.
To broadly summarize the limits of existing technology which this invention mitigates, prior art has addressed the use of algorithm selection or negotiation between two communicating parties, e.g., a client and server or an originator and one or more recipients, during a session establishment “hand-shaking” operation. Other prior art has dealt with the use of replacement algorithms to decrypt and re-encrypt and/or re-hash and/or to apply a replacement or supplemental digital signature to the contents of already existing stored files or messages, in order to reduce the size of those files or messages as stored, or to enhance the security properties as time passes and algorithms become easier to break. Such approaches have not adequately addressed the introduction and support of new encryption/decryption and digital signature cryptographic algorithms that coexist with and interoperate in concert with older legacy algorithms at the time the encrypted and/or digitally signed data is first created.
Prior art has addressed situations for the conversion of a first encryption algorithm to a second encryption algorithm for encrypted communications where the identities of senders and receivers and their specific cryptographic algorithms are all known and are maintained within a centralized database. This database can be queried by a system manager, or manually, to permit identification of user-associated cryptographic algorithms, and the distribution of the shared preferred algorithm to one or both of the parties and its installation in the user's computer. In a typical operation described in prior inventions, the transmission side queries the user identification database and selects an encryption algorithm operated at a transmission side with an encryption algorithm operated at the reception side and transmits the encryption algorithm to the reception side. This encryption algorithm conversion method requires three-party communications and associated delays and service costs to substitute one set of cryptographic algorithms for another. This art does not address the coexistence of mixed digital signature and encryption algorithm environments such as in e-mail, messaging, and collaborative business transactions where the senders and receivers have not previously been known to each other nor agreed to maintain a shared user identification database, or where advanced knowledge of their cryptographic algorithms is not known.
Another existing method for the upgrading and conversion of cryptographic algorithms employs pure replacement methods to increase the encryption strength of previously generated encrypted data stored in a network storage system, by converting the data blocks of the storage system from a first set of cryptographic methods to a second set of stronger cryptographic methods. Such prior art is directed at increasing the security of long term stored data on network storage systems to make it less susceptible to security risks of intrusion by the progressive conversion of blocks of data. Such art does not address issues of providing user transparency for digital signature and encryption applications using both legacy and upgraded cryptographic methods in interactive communications among groups of senders and receivers.
Still other art addresses the upgrading of authentication methods by which users access protected services from a legacy server, by providing a proxy web-based second server to receive user authentication requests from a first legacy server, and forwarding those service requests and the user's credentials to a network-based authentication module or local user database to determine if the user's credentials qualify for access to protected pages on the legacy server. This allegedly simplifies development of more complex and stronger authentication methods by inserting a common protocol between the different clients and their authentication methods, and the proxy web server, which then communicates with the authentication service or user database. This form of art does not address interactive communications among impromptu groups of senders and receivers or user transparency of operations for digitally signed and/or encrypted messages using both legacy and upgraded cryptographic algorithms in open network environments.
In other existent methods for achieving cryptographic algorithm interoperability between senders and receivers, Secure Sockets Layer (SSL) and similar protocols permit the negotiation of the cryptographic algorithms and key lengths to be used, based on the capabilities of the client and the server, on a one-to-one basis, but this is limited to transmission security between the nodes for each single session, and not to the contents communicated through an end-to-end store-and-forward communication system. Secure/Multipurpose Internet Mail Extensions (S/MIME), (RFC 2633) provides a mechanism whereby the selection of the algorithms to be used can be performed on the basis of an S/MIME Capabilities attribute provided by the recipient in a previous message. Only recently (September 2007, in RFC 5008) have the S/MIME standards been extended to deal with the advanced “Suite B” cryptographic algorithms, and no method or means are described or specified, nor does prior art exist to support this technology on legacy applications or operating systems.
Other prior art for upgrading cryptographic algorithms is applied to secure communications systems whereby different cryptographic devices can be inserted back-to-back into each channel of a multi-line trunk to permit automated conversion from one subscriber's cryptographic method, e.g., a legacy method, to another stronger method for a second subscriber's method dictated by their terminal equipments and dialing code protocols. Such art does not apply to more general packet communications networking supported by the Internet and other network architectures, nor does it address interoperability with coexistent legacy and advanced digital signature algorithms.
Prior art also provides post facto solutions for direct substitution of one cryptographic encryption/decryption algorithm by another and re-encryption of the message data or header based on the contents of data in key usage fields provided by the accompanying sender's certificate, and dependent upon system wide standards and policies to enforce uniform substitution, as in the case of a mail server for a community of users. Such a solution does not provide for gradual adoption of improved encryption security methods through transparent interoperability among individuals or ad hoc groups of senders and recipients of both legacy and advanced encrypted communications through the use of dual key certificates whereby one of a set of simultaneously available encryption algorithms can be chosen for decryption based on the capabilities and standards supported by each individual recipient's computer. Prior art does not address methods and apparatus to enable transparent interoperability of digital signature applications using both legacy and improved cryptographic algorithms through means to automatically choose one of a number of simultaneously operable different signing algorithms for communications among communities of users each of whose computer facilities and software only support one of the sets of algorithms.
Overview of the ECC Adoption Problem
One of the primary impediments to the widespread adoption and use of Elliptic Curve Cryptography (ECC) is the lack of availability of ECC certificates, and in particular an ECC key that is embedded within a certificate that is signed using RSA, e.g., using an appropriate self-signed root key and certificate. Although it would be possible to set up a parallel hierarchy of RSA and ECC root certificates and cross-certify them, this additional complexity is in itself an impediment to timely adoption.
One preferred approach would be to use the Microsoft® Windows® Server CA or similar application to issue ECC certificates signed by an RSA key in a very straightforward manner. Unfortunately, it currently appears that this capability is probably not going to be available until the Windows Server (codenamed “Longhorn”) becomes available, which may not be until 2008 or 2009, and is not likely to be widely deployed for several more years after that. At present, it does not seem likely that other ECC-enabled CA products and services will be available from other vendors or trusted third party providers any sooner than that.
In addition, even if some other Certification Authority were able to issue ECC certificates, it would still be a problem to get popular client operating systems and applications, e.g., Microsoft Windows XP and Office 2003, as well as other operating systems and applications such as Linux, Solaris, and others, to process those keys and certificates properly, at least until new operating systems and/or new service packs are released for existing systems to solve the problem. Because the support for the advanced algorithms may be considered an important differentiator and a motivating force to persuade users to upgrade to the latest version of the product, vendors may be reluctant to retrofit their older systems with the new technology.
As a result, an “outside the box” solution is necessary. Several options are possible:
1. It would be possible to encode an ECC certificate in a proprietary manner, by wrapping an ECC key and an elliptic curve digital signature algorithm (ECDSA) signature in what “appears” to be a properly encoded RSA signature field, but one that would be interpreted as the ECDSA signature by an updated middleware component. A “Critical” certificate extension could be included that would cause the certificate validation to fail, except on a system that supported the particular proprietary middleware, which would know how to process that certificate. However, many certificate-processing systems do not process the Critical bit properly, and that might lead to undesirable interoperability problems.
2. One preferred method would include an ECC public key within the “standard” X.509 certificate, as an ECDSA-signed certificate attribute extension, in addition to an RSA key that would be represented normally. With this scheme, the ECC key would be ignored by relying party software that didn't understand the attribute, while the ECC key would be validated only against an ECC chain of signatures, ignoring the RSA chain entirely. This would become a double-use certificate—most users would see and recognize only the RSA key, whereas those with the appropriate software would see the digitally signed ECC key within the certificate hierarchy. However, this approach cannot bind the rest of the content of the certificate including the user's Distinguished Name to the ECC key without a substantial reworking of the standard certificate processing mechanisms within the Certificate Authority program.
3. A certificate request could be generated containing both an RSA and an ECC public key, and sent to the Certificate Authority to be signed. After the signed certificate was generated, thereby proving that the identity of the user had been properly established, another process, e.g., the SPYRUS Signal Identity Manager Registration Authority, could operate as a “certificate creation utility” or a “shadow CA” to create a substitute ECC certificate, relying on the previously created RSA certificate as its authority to do so. The ECC certificate could make use of the same issuer name and serial number, so that revoking the RSA certificate (with a Certificate Revocation List (CRL) or Online Certificate Status protocol (OCSP)) would have the same effect as revoking the ECC certificate, and vice versa. Unfortunately, although this approach solves the problem of creating an ECC certificate, it does little to solve the certificate validation problem within legacy operating systems and applications.
It should, therefore, be appreciated that there is a need for a method of implementing ECC key establishment and digital signatures in accordance with the schemes defined in National Institute of Standards and Technology Special Publication 800-56A (NIST SP 800-56A) and Federal Information Processing Publication FIPS 186-2 in a Microsoft Windows or other general purpose operating system or application environment, despite the lack of support for ECC certificate path validation, as well as the absence of support for ECC primitives. In addition, there is a need for advanced symmetric key algorithms and hash functions, e.g., the Advanced Encryption Standard and the advanced family of Secure Hash Functions (“SHA-2”), that provide cryptographic strength equivalent to the strongest ECC keys. The present invention satisfies these need.